/*
    2012.5.7
    还是求最长公共子串，不同的是这里要求子串在原串中心须是连续的
    这里也用了一些动态规划的思想 。
    复杂度是 O(2*M*N)
*/
#include <iostream>
using namespace std;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define SAME(a,b) ((a)==(b)?1:0)
int main()
{
    char a[] = "hello";
    char b[] = "whel low";
    int opt[10][10] ;

    int lenA = sizeof(a) / sizeof(char);    //这里的len 实际上还包括了\0这个字符
    int lenB = sizeof(b) / sizeof(char);
    int i;
    int j;
    for (i=0; i<lenA-1 ; i++)
    {
        for (j=0; j<lenB-1; j++)
        {
            if (i==0 || j==0)
            {
                opt[i][j] = SAME(a[i],b[j]);
            }
            else
            {   //opt保存的是以a[i]和b[j]为结尾的公共子串
                //要么就是在a[i-1]和b[j-1]的基础上加长1个，要么就是0
                //注意跟普通LCS中的这个opt定义不一样！
                opt[i][j] =  MAX(opt[i-1][j-1] + SAME(a[i],b[j]) , 0);
            }
            cout<<"ai, bj, opt: "<<a[i]<<" "<<b[j]<<" "<<opt[i][j]<<endl;
        }

    }

    for (i=0; i<lenA-1; i++)
    {

        for (j=0; j<lenB-1; j++)
            {
                cout<<opt[i][j]<<", ";
            }
            cout<<endl;
    }

    int max=0;
    for (i=0; i<lenA-1; i++)
        for (j=0; j<lenB-1; j++)
            if (opt[i][j] > max)
                max = opt[i][j];
    cout<<"LCCS():"<<max<<endl;
}
